package datastructure.linklist;

/**
 * @Author ZhangCuirong
 * @Date 2025/8/4 10:04
 * @description:
 */
  public class ListNode {
      public int val;
      public ListNode next;
      public ListNode() {}
      public ListNode(int val) { this.val = val; }
      public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    // 数组转链表，返回链表头节点
    public static ListNode arrayToList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null; // 空数组返回空链表
        }

        // 创建头节点
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;

        // 依次创建后续节点并连接
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }

        return head;
    }

    // 打印链表
    public static void printList(ListNode head) {
        if (head == null) {
            System.out.println("null"); // 空链表直接打印null
            return;
        }

        ListNode current = head;
        StringBuilder sb = new StringBuilder();

        // 拼接链表节点值
        while (current != null) {
            sb.append(current.val);
            if (current.next != null) {
                sb.append(" -> ");
            }
            current = current.next;
        }

        System.out.println(sb.toString());
    }
    // 打印链表并检测是否有环
    public static void printListWithCycleCheck (ListNode head) {
        if (head == null) {
            System.out.println ("链表为空（null），无环");
            return;
        }

// 步骤 1：检测是否有环（快慢指针法）
        boolean hasCycle = false;
        ListNode cycleEntry = null; // 环的入口节点（可选：如需定位入口）
        ListNode slow = head;
        ListNode fast = head;

// 快慢指针判断是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next; // 慢指针走 1 步
            fast = fast.next.next; // 快指针走 2 步
            if (slow == fast) { // 相遇，说明有环
                hasCycle = true;

// （可选）定位环的入口节点：慢指针从头走，快指针从相遇点走，再次相遇即为入口
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                cycleEntry = ptr;
                break;
            }
        }

// 步骤 2：打印链表（若有环，打印到环入口前或标记环）
        StringBuilder sb = new StringBuilder ();
        ListNode current = head;
        int maxPrintSteps = 1000; // 防止无环时无限循环（兜底，可调整）
        int steps = 0;

        if (hasCycle) {
            sb.append ("链表存在环，环入口为节点值：").append (cycleEntry.val).append ("，链表内容：");
// 打印到环入口前的节点，避免无限循环
            while (current != cycleEntry && steps < maxPrintSteps) {
                sb.append (current.val).append ("->");
                current = current.next;
                steps++;
            }
            sb.append (cycleEntry.val).append ("-> ...（进入环，此处省略循环部分）");
        } else {
            sb.append ("链表无环，内容：");
            while (current != null && steps < maxPrintSteps) {
                sb.append (current.val);
                if (current.next != null) {
                    sb.append ("->");
                }
                current = current.next;
                steps++;
            }
// 若触发最大步数，可能是无环但链表过长，或检测逻辑漏判
            if (current != null) {
                sb.append ("-> ...（链表过长，已省略部分节点）");
            }
        }

// 输出结果
        System.out.println (sb.toString ());
    }

    // 测试示例
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        ListNode head = arrayToList(arr);
        System.out.print("链表内容：");
        printList(head); // 输出：1 -> 2 -> 3 -> 4 -> 5

        // 测试 2：有环链表（3 -> 4 -> 5 -> 3 形成环）
        ListNode head2 = new ListNode (1);
        head2.next = new ListNode (2);
        ListNode node3 = new ListNode (3);
        ListNode node4 = new ListNode (4);
        ListNode node5 = new ListNode (5);
        head2.next.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3; // 制造环：5 -> 3
        printListWithCycleCheck (head2); // 输出：链表存在环，环入口为节点值：3，内容：1 -> 2 -> 3 -> ...（进入环）
    }
  }
